#include <iostream>
#include <vector>

using namespace std;
// 该问题如何转换为01背包问题？
// lc1049 最后一块石头的重量 II
int test(vector<int>& stones) {
  vector<int> dp(1501, 0);
  int sum = 0;
  int i, j;
  int target;
  int len = stones.size();
  for (auto& t : stones) sum += t;
  for (i = 0; i < len; i++) {
    target = sum / 2;
    for (j = target; j >= stones[i]; j--) {
      dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
    }
  }
  return sum - dp[target] - dp[target];
}

int main() {
  vector<int> stones{2, 7, 4, 1, 8, 1};
  std::cout << test(stones) << std::endl;
  return 0;
}